home *** CD-ROM | disk | FTP | other *** search
/ Internet Info 1994 March / Internet Info CD-ROM (Walnut Creek) (March 1994).iso / networking / info-service / wais / ir-book-sources / mphf / regenphf.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-04-08  |  3.1 KB  |  117 lines
  1. /********************************  regenphf.c *****************************
  2.  
  3.    Purpose:    Routines to regenerate and use a previously-computed
  4.            minimal perfect hashing function.
  5.  
  6.    Provenance:    Written and tested by Q. Chen and E. Fox, March 1991.
  7.            Edited and tested by S. Wartik, April 1991.
  8.  
  9.    Notes:    None.
  10. **/
  11.  
  12. #include <stdio.h>
  13.  
  14. #include "types.h"
  15. #include "rantab.h"
  16. #include "regenphf.h"
  17. #include "comphfns.h"
  18.  
  19.  
  20. /*************************************************************************
  21.  
  22.     regen_mphf( mphfType*, char* )
  23.  
  24.    Return:    int -- NORM if the MPHF could be reconstructed,
  25.            ABNORM if it couldn't.
  26.  
  27.    Purpose:    Regenerate a MPHF from a specification file.
  28.  
  29.    Notes:    What is regenerated is the table of random numbers.  The
  30.            retrieve() procedure can use these numbers to re-create
  31.         the h0, h1 and h2 values, and from that, the hash value.
  32.  
  33.         If the specification file doesn't seem to correspond
  34.         to the expected format, ABNORM is returned.  However,
  35.         there is no way to tell what caused the error.
  36. **/
  37.  
  38. int regen_mphf( mphf, spec_file_name )
  39.     mphfType    *mphf;              /* out: the regenerated MPHF structure. */ 
  40.     char    *spec_file_name;    /* in: MPHF specification file.        */
  41. {
  42.     int        i;            /* Iterator through vertices.        */
  43.     FILE    *spec_file;
  44.  
  45.     if ( (spec_file = fopen(spec_file_name, "r")) == NULL ) return ABNORM;
  46.  
  47.     if ( fscanf(spec_file, "%d\n%d\n%d\n", 
  48.        &mphf->no_arcs, &mphf->no_vertices, &mphf->seed) != 3 ) {
  49.     fclose(spec_file);
  50.     return ABNORM;        /* File is improperly formatted. */
  51.     }
  52.  
  53.     mphf->gArray = (int*) owncalloc( mphf->no_vertices, sizeof(int) );
  54.  
  55.     for ( i = 0; i < mphf->no_vertices; i++ ) 
  56.     if ( fscanf(spec_file, "%d\n", &mphf->gArray[i] ) != 1 ) {
  57.         fclose(spec_file);
  58.         return ABNORM;    /* File is improperly formatted. */
  59.     }
  60.  
  61.     if ( ! feof(spec_file) ) {
  62.     fclose(spec_file);
  63.     return ABNORM;        /* File is improperly formatted. */
  64.     }
  65.  
  66.     initialize_randomTable( mphf->tables, &mphf->seed );
  67.  
  68.     fclose(spec_file);
  69.  
  70.     return NORM;
  71. }
  72.  
  73.  
  74. /*************************************************************************
  75.  
  76.     release_mphf( mphfType*, char* )
  77.  
  78.    Return:    void
  79.  
  80.    Purpose:    Release the dynamically-allocated storage associated with
  81.            an MPHF.
  82.  
  83. **/
  84.  
  85. void release_mphf( mphf )
  86.     mphfType *mphf;          /* in out: pointer to the MPHF structure.  */ 
  87. {
  88.     free( (char *)mphf->gArray );
  89. }
  90.  
  91.  
  92. /*************************************************************************
  93.  
  94.        retrieve( mphfType*, char* )
  95.  
  96.    Return:    int -- a value in the range 0..mphf->no_arcs-1.
  97.  
  98.    Purpose:    Given an MPHF and a key, return the key's hash value.
  99.  
  100. **/
  101.  
  102. int retrieve( mphf, key )
  103.     mphfType    *mphf;      /* in: the mphf specification.                  */
  104.     char    *key;       /* in: the key, terminated by a null character. */
  105. {
  106.     int        hash;       /* The computed hash value.                     */
  107.     arcType    arc;        /* Storage used to hold the h0, h1 and h2 values. */
  108.  
  109.     compute_h012(mphf->no_arcs, (mphf->no_vertices) / 2, 
  110.          mphf->tables, key, &arc);
  111.     hash = abs(arc.h0 +                
  112.            mphf->gArray[arc.h12[0]] + 
  113.            mphf->gArray[arc.h12[1]] 
  114.            ) % mphf->no_arcs;
  115.     return hash;
  116. }
  117.